/*
 * @lc app=leetcode.cn id=105 lang=cpp
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int>& preorder,int preStart,int perEnd,
                    vector<int>& inorder,int inStart,int inEnd)
        {
            if(preStart > perEnd)
                return NULL;

            int index = -1;
            int leftSize = 0,rightSize = 0;
            for(int i = inStart ; i <= inEnd  ; i++)
            {
                if(preorder[preStart] == inorder[i])
                    {
                        index = i;
                        leftSize = index - inStart;
                    }
            }


            TreeNode *root = new TreeNode(preorder[preStart]);
            root->left = build(preorder,preStart + 1,preStart + leftSize ,inorder,inStart,index -1);
            root->right = build(preorder,preStart+leftSize +1,perEnd,inorder,index+1,inEnd);

            return root;
        }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //前序序列的首位决定根节点，中序进行左右子树的划分        
        return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }
};
// @lc code=end

